package leetcode_900;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 *@author 周杨
 *ReachableNodesInSubdividedGraph_882 给定HP 从0开始出发 每条边都有权重 问所有能到达的顶点个数
 *describe:用迪杰斯特拉 优先队列保存当前最短到达的点 AC 67%
 *2018年11月10日 下午3:49:53
 */
public class ReachableNodesInSubdividedGraph_882 {
	class ANode {
	    int node, dist;
	    ANode(int n, int d) {
	        node = n;
	        dist = d;
	    }
	}

		public int reachableNodes(int[][] edges, int M, int N) {
	        Map<Integer, Map<Integer, Integer>> graph = new HashMap<Integer, Map<Integer, Integer>>();
	        for (int[] edge: edges) {
	            int u = edge[0], v = edge[1], w = edge[2];
	            graph.computeIfAbsent(u, x->new HashMap<Integer, Integer>()).put(v, w);
	            graph.computeIfAbsent(v, x->new HashMap<Integer, Integer>()).put(u, w);
	        }

	        PriorityQueue<ANode> pq = new PriorityQueue<ANode>(
	            (a, b) -> Integer.compare(a.dist, b.dist));
	        pq.offer(new ANode(0, 0));

	        Map<Integer, Integer> dist = new HashMap<Integer, Integer>();
	        dist.put(0, 0);
	        Map<Integer, Integer> used = new HashMap<Integer, Integer>();
	        int ans = 0;

	        while (!pq.isEmpty()) {
	            ANode anode = pq.poll();
	            int node = anode.node;
	            int d = anode.dist;

	            if (d > dist.getOrDefault(node, 0)) continue;
	            ans++;

	            if (!graph.containsKey(node)) continue;
	            for (int nei: graph.get(node).keySet()) {
	                int weight = graph.get(node).get(nei);
	                int v = Math.min(weight, M - d);
	                used.put(N * node + nei, v);
	                int d2 = d + weight + 1;
	                if (d2 < dist.getOrDefault(nei, M+1)) {
	                    pq.offer(new ANode(nei, d2));
	                    dist.put(nei, d2);
	                }
	            }
	        }
	        for (int[] edge: edges) {
	            ans += Math.min(edge[2], used.getOrDefault(edge[0] * N + edge[1], 0) +
	                                     used.getOrDefault(edge[1] * N + edge[0], 0) );
	        }

	        return ans;
    }
}
